Error correction in the Reed-Solomon environment has been implemented in conventional serial architectures which can accommodate a given input data rate in either of two ways. In one approach, the decoder runs at a rate sufficiently high in comparison with the input rate, to assure that the decoder never falls behind the input. This can represent a severe constraint upon input rates. In the other approach, data is delayed by an interval of sufficient length such that "on the average" the decoder is able to keep up with the input. Implicit in this approach is the assumption that worst case situations are sufficiently brief and sufficiently infrequent. The first approach places a limit on achievable throughput while the second approach limits tolerable worst case performance.
Exposition of Reed-Solomon codes may be found in Berlekamp, Algebraic Coding Theory, Agean Park Press (1984). An RS code is succintly described as a block sequence of Galois field symbols where each such field symbol is a field element of the Galois field GF(2.sup.m). Thus each symbol comprises m bits and the length of any such received block sequence is n=2.sup.m -1. The maximum number of erroneous symbols which may be corrected in any such block is given by T and the encoding process creates redundancy in the form of 2T check symbols from k=n-2T message symbols. The block comprises k message symbols and r redundant symbols annexed thereto by the encoder. Thus n=k+r and T is (the integer part of ) r/2. Any such block sequence of symbols may be interpreted as a polynomial C(x), the coefficients of which correspond to the each of the m-bit symbols. A block sequence as above described is a codeword if the polynomial C(x) is a multiple of the generator polynomial g(x) of the code where ##EQU1## The quantity .alpha. is a primitive element of the field and L is an integer which can be selected to simplify the encoding procedure.
The encoding process assures that C(x) will be a codeword, but in the transmission of the block a variety of corrupting influences may be operative to produce a received block of symbols which differs from the encoded information. Within the limits of the code, it is the function of the decoder to detect the introduced errata and to correct same.
In the decoding process for a Reed Solomon code, the following steps are usually performed sequentially:
(a)Power sum symmetric functions are computed from the received codeword. PA1 (b)The key equation is solved to obtain the error location polynomial .sigma.(x) and error value polynomial (x). PA1 (c)The polynomials .sigma.(x) and .omega.(x) are evaluated to ascertain both the locations and the values to add back to the received (erroneous) symbols at the corresponding error locations. PA1 (d)The error value is then added to the erroneous symbol at the error location to correct the error.
All the arithmetical operations implicit in the above prescription are defined on the finite field GF(2.sup.m) as is well known to one of average skill in the art.
Operations as described above are implemented in the prior art with Von Neuman architectures, e.g. systems wherein each sequential operation is a discrete condition precedent for the succeeding operation. Consequently, the allowable complexity of a process in such an implementation bears a rather direct relationship to the time available for such process. Instruction overlap and pipelining are approaches which achieve some substantial improvement over the strict Von Neuman model, but it may be observed that the implementation of operations is not expensive in semiconductor hardware, whereas the number and density of interconnections is both an economic and physical limitation. As a result of VLSI technology, systolic arrays provide an alternative form of architecture especially attractive for application to error correction problems.
An RS decoder is known which operates at a serial channel rate of 120 Mbps, achieving a coding gain of 3.3 db at an input bit error rate of 10.sup.-6. The performance of this decoder, (Cyclotomics Model 120) is known to experience degradation when subject to continuous worst case data. The present invention represents an increase in output channel rate by a factor of as much as about 17 over the aforementioned Model 120. This is accomplished in the first instance by a highly parallel architecture and further, by an implementation in GaAs integrated circuits as below described.
In the art, a systolic architecture is characterized by clocked propagation of information through a series of rather similar stages, each of which provides some simple incremental processing step. By a hypersystolic architecture, there is meant a systolic arrangement in which control information, including clocking, propagates serially together with the data through the various elements of the system. Thus, there is no requirement that global synchrony be maintained between the several integrated devices of the system.